package com.leetcode.partition17;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/11/3 10:48
 */
public class LC1631最小体力消耗路径 {

    private static final int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public static int minimumEffortPath(int[][] heights) {
        return dijkstra(heights);
    }

    public static void main(String[] args) {
//        int[][] heights = {
//                {1, 2, 2},
//                {3, 8, 2},
//                {5, 3, 5}
//        };
        int[][] heights = {
                {1, 2, 1, 1, 1},
                {1, 2, 1, 2, 1},
                {1, 2, 1, 2, 1},
                {1, 2, 1, 2, 1},
                {1, 1, 1, 2, 1}
        };
        System.out.println(minimumEffortPath(heights));
    }

    private static int dijkstra(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        boolean[][] visited = new boolean[m][n];
        //优先队列保证每次出来的都是目前差值最小的  <[x, y, 到达heights[x][y]最大路径高度差值]>
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        //加入起点，起点就是终点的话差值就是0
        minHeap.add(new int[]{0, 0, 0});
        while (!minHeap.isEmpty()) {
            int[] cur = minHeap.poll();
            int x = cur[0], y = cur[1], maxValue = cur[2];
            //如果当前节点被访问过就不能继续，避免死循环
            if (visited[x][y]) continue;
//            System.out.printf("(%d, %d, %d) start\n", x, y, maxValue);
            //优先队列根据最大路径差值进行poll，poll出来的如果是终点，就说明已经找到了最小体力消耗的路径，结果就是最小路径上的最大路径高度差值
            if (x == m - 1 && y == n - 1) return maxValue;
            visited[x][y] = true;
            for (int[] dir : dirs) {
                int x1 = x + dir[0], y1 = y + dir[1];
                //邻节点的边界处理
                if (x1 < 0 || x1 >= m || y1 < 0 || y1 >= n) continue;
                //到达邻接点的最大路径高度差值只依赖了当前节点和邻节点的高度差，也就是heights[x][y]-heights[x1][y1]，而maxValue为到达(x, y)的最大路径高度差值，
                //maxValue在到达(x1, y1)之前已经计算过。根据题目要求，每一个邻接点都需要更新到达邻接点的最大路径高度差值，取最大值
                minHeap.add(new int[]{x1, y1, Math.max(Math.abs(heights[x][y] - heights[x1][y1]), maxValue)});
//                System.out.printf("(%d, %d, %d)\n", x1, y1, Math.max(Math.abs(heights[x][y] - heights[x1][y1]), maxValue));
            }
        }
        return 0;
    }
}
